#include <iostream>
#define _  ios_base::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using namespace std;
const ll mod=9973;

int n;
struct Matrix{
	static const int maxn=15;
	ll tmp[maxn][maxn];
	Matrix(ll e=0){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				tmp[i][j]=e*(i==j);
	}
	Matrix mul(Matrix A,Matrix B){
		Matrix ans(0);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				for(int k=1;k<=n;k++){
					ans.tmp[i][j]=(ans.tmp[i][j]+(A.tmp[i][k]*B.tmp[k][j])%mod)%mod;
				} 
			}
		}
		return ans;
	}
	Matrix qpow(Matrix A,ll b){
		Matrix ans(1);
		while(b){
			if(b&1)
				ans=mul(ans,A);
			b>>=1;
			A=mul(A,A);
		}
		return ans;
	}
}mat;
int main(){
	_;
	ll t;
	cin>>t;
	while(t--){
		ll m;
		cin>>n>>m;
		ll out=0;
		for(ll i=1;i<=n;i++){
			for(ll j=1;j<=n;j++){
				cin>>mat.tmp[i][j];
			}
		}
		mat=mat.qpow(mat,m);
		for(ll i=1;i<=n;i++){
			out=(out+mat.tmp[i][i])%mod;
		}
		cout<<out<<endl;
	} 
	return 0;
}
